MPRI - Parisian Master of Research in Computer Science
Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming
Nicolas SCHABANEL, CNRS - Université Paris Diderot
LECTURE 3 (2016/09/28)
MATHEMATICAL PROGRAMMING 2: SEMI-DEFINITE/VECTOR PROGRAMMING
Lecture 3:
[0:00:00] 0. Introduction
[0:02:09] 1. A quadratic program for Max-CUT
[0:10:17] 2. Relaxing a Quadratic Program as a Vector Program
[0:16:14] 3. Vector Programs = Semi-Definite Programs
[0:27:28] 4. VP is indeed a relaxation of integer QP
[0:38:43] 5. Rounding VP: the Random Hyperplane Technic
[1:10:09] 6. Analysis of the Random Hyperplane Algorithm
Exercice Session 3:
[1:31:47] 7. Exercise HW2-1: A Dumb Algorithm for Max-SAT
[1:39:12] 8. Exercise HW2-3: SDP-Approximation for Max-2SAT
